package Hot100;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

// 排序遍历 O(Nlogn)
// HashSet O(N)

public class 最长连续序列_128 {
    public int longestConsecutive(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int i = 1, count = 1, ret = 0;
        if (n < 2) return n;
        while (i < n) {
            if (nums[i - 1] != nums[i]) {
                if (nums[i - 1] + 1 == nums[i]) {
                    count++;
                } else {
                    ret = Math.max(ret, count);
                    count = 1;
                }
            }
            i++;
        }
        ret = Math.max(ret, count);
        return ret;
    }


    public int longestConsecutive2(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int n : nums) set.add(n);

        int ans = 0;
        for (int num : set) {
            int cur = num;
            if (!set.contains(cur - 1)) {
                while (set.contains(cur + 1)) {
                    cur++;
                }
            }
            ans = Math.max(ans, cur - num + 1);
        }
        return ans;
    }
}
